package _interview100;

import java.util.ArrayList;
import java.util.List;

/**
 * 79. 单词搜索
 */
public class No79 {
    private char[][] board;
    private String word;
    private List<String> path;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.path = new ArrayList<>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(word.length() - 1) && dfs(word.length() - 1, i, j)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int i, int row, int column) {
        if (i < 0) return true;
        else if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || board[row][column] != word.charAt(i) || path.contains(row + "_" + column))
            return false;
        else {
            path.add(row + "_" + column);
            boolean b = dfs(i - 1, row, column - 1) ||
                    dfs(i - 1, row, column + 1) ||
                    dfs(i - 1, row - 1, column) ||
                    dfs(i - 1, row + 1, column);
            path.remove(path.size() - 1);
            return b;
        }
    }
}
